﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphSpace
{
    class GoalDirectedSearch
    {
            BinaryHeap heap;
            public GoalDirectedSearch(int StartKnoten, int ZielKnoten)
            {
                heap = new BinaryHeap();
            }


            private double search(Graph G, Knoten initialKnoten, Knoten zielKnoten, out Knoten[] path)
            {
                for (int i = 0; i < G.V.Count; i++)
                {
                    heap.insert(G.V[i]);
                }

                while (!heap.isEmpty())
                {
                    Knoten aktKnoten = heap.extractHead();
                    if (aktKnoten.id == zielKnoten.id)
                        break;
                    aktKnoten.besucht = true;
                    for (int i = 0; i < G.A[aktKnoten.id].Count; i++)
                    {
                       Knoten ZielKnoten = G.A[aktKnoten.id][i].Vnach;
                        if (!ZielKnoten.besucht)
                        {
                            // neue abstandsberechnung fuer AStar
                            //int NewDist = aktKnoten.distance + (int)G.E[aktKnoten.Id][i].Gewicht;
                            int AbstandX =  zielKnoten.x - G.A[aktKnoten.id][i].Vvon.x;
                            int AbstandY = zielKnoten.y - G.A[aktKnoten.id][i].Vvon.y;
                            double NewDist = aktKnoten.distance + (int)G.A[aktKnoten.id][i].Gewicht + (int)Math.Sqrt(AbstandX * AbstandX + AbstandY * AbstandY);                
                            if (NewDist < G.A[aktKnoten.id][i].Vnach.distance)
                            {
                                ZielKnoten.predeseccor = aktKnoten;
                                heap.decreaseKey(ZielKnoten, NewDist);
                                ZielKnoten.realdist = aktKnoten.realdist + G.A[aktKnoten.id][i].Gewicht;
                            }
                        }
                    }

                }
                Knoten pred = zielKnoten;
                List<Knoten> Path = new List<Knoten>();
                while (pred != null)
                {
                    Path.Add(pred);
                    pred = pred.predeseccor;
                }

                Path.Reverse();
                path = Path.ToArray();
                return zielKnoten.realdist;
            }


    }
}
